package com.itheima.apitest.binarysearch;

/* 在数组{1,2,3,4,5,6,7,8,9,10}中,查找某个元素c的位置
        - 实现步骤
        1. 定义两个变量，表示要查找的范围。默认min = 0 ，max = 最大索引
        2. 循环查找，但是min <= max
        3. 计算出mid的值
        4. 判断mid位置的元素是否为要查找的元素，如果是直接返回对应索引
        5. 如果要查找的值在mid的左半边，那么min值不变，max = mid -1.继续下次循环查找
        6. 如果要查找的值在mid的右半边，那么max值不变，min = mid + 1.继续下次循环查找
        7. 当min > max 时，表示要查找的元素在数组中不存在，返回-1.
*/
public class BinarySearchTest {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};
        int number = 9;

        int index = binarySearchForIndex(arr,number);
        System.out.println(index);

    }

    private static int binarySearchForIndex(int[] arr, int number) {
        //1. 定义两个变量，表示要查找的范围。默认left = 0 ，right = 最大索引
        int left = 0;
        int right = arr.length-1;
        //2. 循环查找，但是left <= right
        while (left <= right){
            //3. 计算出mid的值
            int mid = (right + left) >>> 1;
            //4. 判断mid位置的元素是否为要查找的元素，如果是直接返回对应索引
            //5. 如果要查找的值在mid的左半边，那么left值不变，right = mid -1.继续下次循环查找
            if (arr[mid] > number){
                right = mid - 1;
            }
            //6. 如果要查找的值在mid的右半边，那么right值不变，left = mid + 1.继续下次循环查找
            if (arr[mid] < number){
                left = mid + 1;
            }
            else {
                return mid;
            }
        }
        //7. 当left > right时，表示要查找的元素在数组中不存在，返回-1.
        return -1;
    }
}
